#define _CRT_SECURE_NO_WARNINGS 1
#include"dun.h"

void dunInit(sl* p)
{
	assert(p);
	p->a = NULL;
	p->cap = p->size = 0;
}

void dunpush(sl* p, dataty x)
{
	assert(p);
	if (p->size == p->cap)
	{
		int new = p->cap == 0 ? 4 : p->cap * 2;
		sl* w = (sl*)realloc(p->a, sizeof(sl) * new);
		p->a = w;
		p->cap = new;
	}
	p->a[p->size] = x;
	p->size++;
	adjust(p->a, p->size - 1, p->size);
}
void adjust(int* c,int child,int m)
{
	assert(c);
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (c[child] < c[parent])
		{
			int tem = c[child];
			c[child] = c[parent];
			c[parent] = tem;
		}
		else break;
		child = parent;
		parent = (child - 1) / 2;
	}
}
void heapprintf(sl* p)
{
	int i = p->size - 1;
	int m = 0;
	while (m <= i)
	{
		printf("%d ", p->a[m]);
		m++;
	}
}
bool heapempty(sl* p)
{
	assert(p);
	return p->size == 0;
}
int heapsize(sl* p)
{
	assert(p);
	return p->size;
}
void heappop(sl* p)
{
	assert(p);
	assert(!heapempty(p));
	heapswap(&p->a[0], &p->a[p->size - 1]);
	p->size--;
	justdown(p->a, p->size, 0);
}
void justdown(int* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (a[child + 1] < a[child] && child + 1 < n)
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			heapswap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else break;
	}
}
void heapswap(int* p, int* q)
{
	int tem = *p;
	*p = *q;
	*q = tem;
}
void printtop(int* a, int max, int num)
{
	sl q;
	dunInit(&q);
	for (int i = 0; i < num; ++i)
	{
		dunpush(&q, a[i]);
	}
	for (int i = num; i < max; i++)
	{
		if (a[i] > heaptop(&q))
		{
			heappop(&q);
			dunpush(&q, a[i]);
			
		}
	}
	heapprintf(&q);
}

dataty heaptop(sl* p)
{
	return p->a[0];
}